\section{Partial Tree}
\label{sec:partialtree}

For high-performance data processing, a common idea is to divide a large amount of data into smaller fragments and distribute them to multiple processors for later processing.
Consider an XML tree in Fig.~\ref{fig:xmltree} and its serialized document is divided into the following chunks (chunk$_0$ to chunk$_3$ in document order).
When an XML document is divided, we could parse a chunk to construct a subgraph (a sequence of subtrees). 
For example, given chunk$_2$, we can construct a subgraph as shown in Figure~\ref{fig:graphtree}.
However, because of the intrinsic tree structure of XML documents, queries cannot be directly evaluated on them after splitting. 
For example, we cannot select the children of b2 on the subgraph from chunk$_2$, because the path from the root of the subgraph to the root of the whole tree is missing.


\begin{flushleft}
	chunk$_0$:~\texttt{<r><b><d><c>txt1</c></d><a at="1"></a></b><b><d>}\\
	chunk$_1$:~\texttt{<c>txt2</c><d><c>txt3</c></d></d><a at="2"></a><d>}\\
	chunk$_2$:~\texttt{<c>txt4</c><c>txt5</c></d><a at="3"></a></b><b><d>}\\
	chunk$_3$:~\texttt{<c>txt6</c></d><d><d><c>txt7</c></d></d></b></r>}
\end{flushleft}


\begin{figure}[t]
	\begin{minipage}[b]{.5\textwidth}
		\centering
		\includegraphics[width=0.9\linewidth]{figures/figures-1.pdf}
		\caption{An example XML tree.}
		\label{fig:xmltree}
	\end{minipage}%
	\begin{minipage}[b]{.5\textwidth}
		\centering
		\includegraphics[width=.4\linewidth ]{figures/figures-13.pdf}
		\caption{A subgraph from chunk$_2$.}
		\label{fig:graphtree}
	\end{minipage}
\end{figure} 

To cope with the path-missing issue, we exploit a data structure called
\emph{partial tree}~\cite{HaMa16} that is suitable for representing chunked XML data
of an XML documents. A partial tree can be constructed in two steps: we first
parse a chunk of an XML document to generate a sequence of subtrees, and then add the path for
each root of subtrees to the root of the original XML tree. For example, four
partial trees are constructed from parsing chunk$_0$ to chunk$_3$ as shown in
Figure~\ref{fig:partialtree}. A partial tree corresponding to a chunk is the
minimum subgraph, that satisfies three conditions:

\begin{itemize}
	\item a subgraph is connected, which means a subgraph is a tree.
	\item a subgraph contains the root of the original XML tree. 
	\item elements(tag/attribute/text) from the same chunk are in the same subgraph.
\end{itemize}


A concrete algorithm for this computation is given in \cite{HaMa16}
(Algorithm 0). In this study, the chunks of a divided XML document begin at either a start tag or an end
tag to keep the attributes and texts as closed nodes. It is useful to
distinguish the four cases that a node in a partial tree has or does not have
its tags in the corresponding chunk. Nodes in a partial tree are categorized
into the following four types (in Figure~\ref{fig:nodetypes}) based on the
inclusion of tags in the chunk: a \emph{closed node} with both its tags, a
\emph{left-open node} with only its end tag, a \emph{right-open node} with only
its start tag, and a \emph{pre-node} with no tags. The left-open nodes,
right-open nodes and pre-nodes are called \emph{open nodes}.

\begin{figure}[t]
	\centering
	\includegraphics[scale=.8]{figures/figures-2.pdf}\qquad
	\includegraphics[scale=.8]{figures/figures-3.pdf}\qquad
	\includegraphics[scale=.8]{figures/figures-4.pdf}\qquad
	\includegraphics[scale=.8]{figures/figures-5.pdf}\\[2pt] 
	\makebox[55pt][c]{pt1}\qquad
	\makebox[55pt][c]{pt2}\qquad
	\makebox[55pt][c]{pt3}\qquad
	\makebox[55pt][c]{pt4}\qquad
	\caption{ Four partial trees constructed from chunks.}
	\label{fig:partialtree}
\end{figure}

\begin{figure}[t]
	\centering
	\includegraphics[width=.99\linewidth]{figures/nodetypes.png}
	\caption{Node types.}
	\label{fig:nodetypes} 
\end{figure} 